/*
* $Id: malloc.c,v 1.21 2007/10/23 07:52:05 sunny Exp $
*/

#if defined(__K0__)
#pragma section @@DATA @@IXDATA
//#pragma inline  // enable memcpy() and memset() with direct inline expansion instead of function call
#endif //#if defined(__K0__)

#include "unet.h"
#include "debug.h"
#include "type.h"
#include <stdlib.h>
#include <string.h>

#if DEBUG_MODE
    #include <stdio.h>
    #if 0
	#undef  DBG_printf
	#define DBG_printf(P)
    #endif

    #if 0
	#undef  TRACE_TAG
	#define TRACE_TAG()
	#undef  TRACE_puts
	#define TRACE_puts(s)
	#undef  TRACE_printf
	#define TRACE_printf(P)
    #endif
#endif

#if 1

#define MAX_MEMORY	(MemPoolSize - 1)
#define LIST_ITEMS	(MemPoolSize / 20)

// using a fixed size array isn't the best idea,
// the best implementation would be to manage the data with a chained list

typedef struct _list_item_ {
	size_t size;
	size_t first_byte_ptr;
} list_item;

static list_item list[LIST_ITEMS];
static list_item allocated[LIST_ITEMS];

#if DEBUG_MODE
static INT16 balance_cnt = 0;
static UINT16 total_cnt = 0;
static UINT16 malloc_cnt = 0;
static UINT16 free_cnt = 0;
#endif

size_t init_malloc_vars(void)
{
#if DEBUG_MODE
//	balance_cnt = total_cnt = malloc_cnt = free_cnt = 0;
#endif

	memset(&list, 0, sizeof(list));
	memset(&allocated, 0, sizeof(allocated));

// 2007/3/21 13:05:25, Sunny: TODO: auto detect the maximum available heap memory

	return( list[0].first_byte_ptr = (size_t) sbrk( list[0].size = MAX_MEMORY ) );
}

void *malloc(size_t size) {
	int i, k;
	void *current;

	DBG_printf(("\r#%04u(%2d) malloc #%04u: sz=%02x (%u)", ++total_cnt, ++balance_cnt, ++malloc_cnt, size, size));

	k = LIST_ITEMS;
	for( i = 0 ; i < LIST_ITEMS ; i++ ) {
		if( list[i].size == size ) {	// best match
		        k = i;
		//	TRACE_puts("malloc: best match");
			break;
		}
		if( list[i].size > size && k == LIST_ITEMS ) {	// big enougth
		        k = i;
		//	TRACE_puts("malloc: big enougth");
		}
	}

	if( k == LIST_ITEMS ) {
	        TRACE_puts("malloc: no suitable block found");
		return NULL;
	}
	i = k;

	for( k = 0 ; k < LIST_ITEMS ; k++ ) {
		if( allocated[k].size == 0 ) {
			break;
		}
	}

	if( k == LIST_ITEMS) {
	        TRACE_puts("malloc: no allocated slots");
		return NULL;
	}

	current = (void *)list[i].first_byte_ptr;
	if(current) {
		list[i].first_byte_ptr += size;
		list[i].size -= size;

		allocated[k].first_byte_ptr = (size_t)current;
		allocated[k].size = size;
		DBG_printf((": %p", current));

		if(current < (void *)0xE000) {
			current = NULL;		// Should never come here, otherwise, it is a program bug.
		}
	}
	else {
	        TRACE_printf(("malloc: ptr=%p, sz=%02x, i=%d", current, size, i));
	        NOP();	// for break point setting.
	}

	return current;
}

void free(void *ptr) {
	int i, k;

	DBG_printf(("\r#%04u(%2d)   free #%04u: %p",++total_cnt, --balance_cnt, ++free_cnt, ptr));
	if(!ptr) {
	        TRACE_TAG();
	        return;
	}

	for( i = 0 ; i < LIST_ITEMS ; i++ )
		if( allocated[i].first_byte_ptr == (size_t)ptr )
			break;

	if(i == LIST_ITEMS) {
		DBG_puts(", not allocated ptr!");
		return;
	}

	for( k = 0 ; k < LIST_ITEMS ; k++ ) {
		if((list[k].first_byte_ptr - allocated[i].size) == (size_t)ptr) {
			list[k].size += allocated[i].size;
			list[k].first_byte_ptr = (size_t)ptr;
			break;
		}

		if( list[k].size == 0 ) {
			list[k].size = allocated[i].size;
			list[k].first_byte_ptr = allocated[i].first_byte_ptr;
			break;
		}
	}

	if(k == LIST_ITEMS) {
		DBG_puts(", no list slot!");
		return;
	}

#if 1 // DEBUG_MODE
	allocated[i].first_byte_ptr = 0;
#endif
	allocated[i].size = 0;
}
#endif

/*
Source URL: http://www.osdcom.info/content/view/31/39/

Simple Memory Allocation Algorithms
Sunday, 26 March 2006
Have you got stucked in the development while aiming to implement a modern and
very efficient alorithm? Here's a start up point before getting to implement
them.


Simple Memory Allocation Algorithms

Memory allocation is a process that assigns chunks of memory upon request of the
various processes running on a machine. Today, there are several well known
efficient algorithms used on high-end operating systems but their mathematical
models are quite difficult to comprehend from the first time by most amateur
operating system developers. That's why most of the simple operating systems
available on the amateur websites use less efficient memory allocation
algorithms but highly comprehensible and very educative.

This article focuses on three simple algorithms you may want to experiment on
your osdev projects.

The Simplest Algorithm

The complexity of an algorithm is given by the number of steps, their iteration
and their timing. Since we are talking about the simplest one, it will have the
fastest memory release function: it will do nothing!

The allocator will just store the address of the next free available memory
block and allocate requested chunks continuously. A brief implementation
follows:




#define MAX_MEMORY 1024 * 1024 * MEMORY_SIZE_IN_MEGABYTES

int peak;

void *malloc(size_t size) {
	void *current;
if( MAX_MEMORY - peak < size ) return null;
	current = (void *)peak;
	peak += size;
	return current;
}

void free(void *ptr) {
	return;
}




Extremely inefficient, but stable, no different block will overlap to cause
memory sharing violations. Since the memory will be consumed after a certain
number of allocations, we must implement a mechanism to re-enter the released
blocks back in a list of available locations.

The "First Fit" Algorithm

The first fit algorithm basically extends the previous one by implementing a
list of free blocks. When the allocator will receive a request of X bytes, it
will lookup the list for an available block to fit X bytes. Since aiming to find
a perfect match my yield negative results we will allocate memory for the X
bytes in the first block equal or greater than X.

Of course, this will lead to an undesired effect: memory fragmentation. Larger
block will be split into smaller ones to fit the requested amounts of memory and
we may end up with the impossibility of serving a process requesting Y bytes
although the sum of all free, but small, blocks is way greater than Y.

A brief C-like implementation follows.




#define MAX_MEMORY 1024 * 1024 * MEMORY_SIZE_IN_MEGABYTES
// using a fixed size array isn't the best idea,
// the best implementation would be to manage the data with a chained list
#define LIST_ITEMS 100

typedef struct {
	size_t size;
	size_t first_byte_ptr;
} list_item;

list_item list[LIST_ITEMS];
list_item allocted[LIST_ITEMS];

int j = 0;

void *malloc(size_t size) {
	int i;
	void *current;

	if( j < LIST_ITEMS ) return null; // no slots

	for( i = 0 ; i < LIST_ITEMS ; i++ )
		if( list[i].size >= size ) break;

	if( i == LIST_ITEMS ) return null; // no suitable block found

	current = (void *)list[i].first_byte_ptr;
	list[i].first_byte_ptr += size;
	list[i].size -= size;

	allocated[j].first_byte_ptr = current;
	allocated[j].size = size;
	j++;

	return current;
}

void free(void *ptr) {
	int i;

	for( i = 0 ; i < LIST_ITEMS ; i++ )
		if( allocated[i].first_byte_ptr == ptr ) break;

	for( k = 0 ; k < LIST_ITEMS ; k++ )
		if( list[k].size == 0 ) break;

	list[k].size = allocated[i].size;
	list[k].first_byte_ptr = allocated[k].first_byte_ptr;

	allocated[i].first_byte_ptr = 0;
	allocated[i].size = 0;

	return;
}




There is enough room for optimization for the above code, especially for the
management of the two lists. Chained links are optimal and sorting them when the
CPU is idle is a good idea, especially if followed by testing if any blocks are
adjacent in order to be merged.

The "Buddy" Algorithm

The buddy algorithm is an optimized version of the "first fit" allocator. It
will only allocate blocks of certain sizes, maintaining lists for each series of
blocks of a specific size. The permitted sizes are often powers of two, aiming
to match blocks of basic types which have sizes of powers of two and because
splitting a lager block in two will result a pair of permitted blocks of
inferior permitted size. Some implementations use other series of sizes, such as
the Fibonacci sequence.

The main advantage compared to "first fit" is speed. We know exactly where to
lookup for free blocks, and if we don't find one we go straight to the next
list, of larger blocks. But as its ancestor, it suffers from memory
fragmentation.

Let's suppose a process requests a block of 7 bytes. The allocator will
automatically lookup the list of 8 bytes blocks and assign one. There will be a
one byte loss in the allocated block. But what if the process then requests a
block of 9 bytes? It will look up the 16 bytes block list and return one block.
The loss will consist in 7 unused bytes.

That may not sound very tragic, but multiply the amounts with 1K or 1MB to get
the figures quite closed to the reality. The lost memory space is common known
as slack space. Fragmentation can be reduced by making the block sizes closer
together.
*/

/*
Source URL: http://en.wikipedia.org/wiki/Fibonacci_number

Fibonacci number:

That is, after two starting values,each number is the sum of the two preceding
numbers. The first Fibonacci numbers denoted as Fn, for n = 0, 1, ..., are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,
4181, 6765, 10946, 17711, 28657, 46368, 75025 ...

Sometimes this sequence is considered to start at F1 = 1, but it is more common
to include F0 = 0.
*/
